﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace ImryStefanVRP
{
    public class NeighboorhoodSearches
    {
        /// <summary>
        /// Finds a single good move in the neighborhood. Returns the change so it is possible to undo.
        /// </summary>
        internal static ChangeInSolution GetGoodSolutionInANeighborhood(CVRPSolution currentSolution)//internal function is much faster-Edwin
        {
            List< ChangeInSolution> theList = new List<ChangeInSolution>();

            for (int ok = 0; ok < Program.vrpData.Dimension * Program.vrpData.Dimension; ok++) // Choose 1st route
            {
                int i = Program.rand.Next(currentSolution.listOfRoutes.Count);
                int j = Program.rand.Next(currentSolution.listOfRoutes.Count);
                // just randomly choose the 
                if (i != j)
                {   //randomly choose the node to swap -Edwin
                    int k = 1 + Program.rand.Next(currentSolution.listOfRoutes[i].GetNumberOfNodesVisited());
                    int l = 1 + Program.rand.Next(currentSolution.listOfRoutes[j].GetNumberOfNodesVisited());

                    // Swaps work only if the both nodes chosen are not depots. Also they are symmetric
                    if (i < j && l <= currentSolution.listOfRoutes[j].GetNumberOfNodesVisited() && k <= currentSolution.listOfRoutes[i].GetNumberOfNodesVisited())
                    {
                        ChangeInSolution aSwap = GenerateAswap(i, j, k, l, currentSolution); //aswap does not contain the array information? 
                        if (aSwap.thisMoveType != MoveType.NoMove)
                        {
                            for (int listIndex = 0; listIndex < theList.Count; listIndex++)
                            {
                                if (theList[listIndex].totalCostAfterChange > aSwap.totalCostAfterChange)
                                {
                                    theList.Insert(listIndex, aSwap);
                                    break;
                                }
                            }
                            if (theList.Count == 0)
                                theList.Add(aSwap);
                        }
                    }

                    // Injections into 2nd route require starting with a node which is not a depot
                    if (k <= currentSolution.listOfRoutes[i].GetNumberOfNodesVisited())
                    {
                        ChangeInSolution anInjection = GenerateAnInjection(i, j, k, l, currentSolution);
                        if (anInjection.thisMoveType != MoveType.NoMove)
                        {
                            for (int listIndex = 0; listIndex < theList.Count; listIndex++)
                            {
                                if (theList[listIndex].totalCostAfterChange > anInjection.totalCostAfterChange)
                                {
                                    theList.Insert(listIndex, anInjection);
                                    break;
                                }
                            }
                            if (theList.Count == 0)
                                theList.Add(anInjection);
                        }
                    }
              
                }
                if (theList.Count == 20) // ??-Edwin
                    theList.RemoveAt(19);
            }
            if (theList.Count > 0)
            {
                // Generate a Poisson Random Variable with mean 1
                double p = 1, L = Math.Exp(-1);
                int k = 0;
                do
                {
                    k++;
                    p = Program.rand.NextDouble();
                }
                while (p > L);

                ChangeInSolution theChangeToBeMade = theList[Math.Min(k - 1, theList.Count() - 1)];
                currentSolution.ApplyChange(theChangeToBeMade);
                return theChangeToBeMade;
            }
            else
                return new ChangeInSolution(currentSolution.totalCost);
        }

        /// <summary>
        /// A random perturbation of the solution. Not possible to undo, so it doesn't return anything.
        /// </summary>
        internal static void HugeJump(CVRPSolution currentSolution)
        {
            for (int ok = 0; ok < Math.Sqrt(Program.vrpData.Dimension); ok++)
            {
                int i = Program.rand.Next(currentSolution.listOfRoutes.Count);
                int j = Program.rand.Next(currentSolution.listOfRoutes.Count);
                if (i < j)
                {
                    int k = 1 + Program.rand.Next(currentSolution.listOfRoutes[i].GetNumberOfNodesVisited() - 1);
                    int l = 1 + Program.rand.Next(currentSolution.listOfRoutes[j].GetNumberOfNodesVisited() - 1);

                    ChangeInSolution aSwap = GenerateAswap(i, j, k, l, currentSolution);

                    if (aSwap.thisMoveType == MoveType.Swap)
                        currentSolution.ApplyChange(aSwap);
                }
            }
        }

        private static ChangeInSolution GenerateAswap(int i, int j, int k, int l, CVRPSolution currentSolution)
        {
            ChangeInSolution aSwap = new ChangeInSolution(currentSolution.totalCost);

            aSwap.nextDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute - Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)] + Program.vrpData.Demands[currentSolution.listOfRoutes[j].GetNodeAt(l)];
            aSwap.nextDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute - Program.vrpData.Demands[currentSolution.listOfRoutes[j].GetNodeAt(l)] + Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)];

            if (aSwap.nextDemandOnA <= Program.vrpData.Capacity &&
               aSwap.nextDemandOnB <= Program.vrpData.Capacity)
            {
                aSwap.thisMoveType = MoveType.Swap;
                aSwap.prevDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute;
                aSwap.prevDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute;

                aSwap.nextDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k - 1), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k), currentSolution.listOfRoutes[i].GetNodeAt(k + 1)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k - 1), currentSolution.listOfRoutes[j].GetNodeAt(l)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l), currentSolution.listOfRoutes[i].GetNodeAt(k + 1)];
                aSwap.nextDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[j].GetNodeAt(l)]
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l), currentSolution.listOfRoutes[j].GetNodeAt(l + 1)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k), currentSolution.listOfRoutes[j].GetNodeAt(l + 1)];
                aSwap.prevDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute;
                aSwap.prevDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute;

                aSwap.routeA = i;
                aSwap.routeB = j;
                aSwap.spotA = k;
                aSwap.spotB = l;

                aSwap.totalCostAfterChange = aSwap.totalCostBeforeChange + aSwap.nextDistOnA + aSwap.nextDistOnB - aSwap.prevDistOnA - aSwap.prevDistOnB;
            }
            return aSwap;
        }

        private static ChangeInSolution GenerateAnInjection(int i, int j, int k, int l, CVRPSolution currentSolution)
        {
            ChangeInSolution anInjection = new ChangeInSolution(currentSolution.totalCost);

            anInjection.nextDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute
                                         - Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)];
            anInjection.nextDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute
                                         + Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)];

            if (anInjection.nextDemandOnB <= Program.vrpData.Capacity)
            {
                if (currentSolution.listOfRoutes[i].GetNumberOfNodesVisited() == 1)
                    anInjection.thisMoveType = MoveType.InjectionWhichRemovesARoute;
                else
                    anInjection.thisMoveType = MoveType.InjectionWhichPerservesBothRoutes;

                anInjection.prevDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute;
                anInjection.prevDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute;

                anInjection.nextDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute
                         + Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k + 1), currentSolution.listOfRoutes[i].GetNodeAt(k - 1)]
                         - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k), currentSolution.listOfRoutes[i].GetNodeAt(k - 1)]
                         - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k + 1), currentSolution.listOfRoutes[i].GetNodeAt(k)];
                anInjection.nextDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute
                         + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                         + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                         - Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[j].GetNodeAt(l)];
                anInjection.prevDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute;
                anInjection.prevDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute;

                anInjection.routeA = i;
                anInjection.routeB = j;
                anInjection.spotA = k;
                anInjection.spotB = l;

                anInjection.totalCostAfterChange = anInjection.totalCostBeforeChange + anInjection.nextDistOnA + anInjection.nextDistOnB - anInjection.prevDistOnA - anInjection.prevDistOnB;
            }
            return anInjection;
        }
      
        //shuffles half of a random route to pertubate and get out of local maxima
        public static void Shuffle(int i, CVRPSolution currentSolution)
        {
            int routeindextoshuffle = i;  
            //create the half-route that we will shuffle
            List<int> halftoshuffle = new List<int>(currentSolution.listOfRoutes[routeindextoshuffle].nodesArray);    
            halftoshuffle.Remove(0); //remove depot from beginning and end
            halftoshuffle.Remove(0);
            int totallength = halftoshuffle.Count; 
            string halflengthstring =  Math.Floor(0.5*halftoshuffle.Count).ToString();
            int halflength;
            int.TryParse(halflengthstring, out halflength);
            for (int j = halflength + 1; j <= totallength; j++)
            {
                halftoshuffle.RemoveAt(halftoshuffle.Count - 1);             
            }
            //create the half-route that we will keep
            List<int> halftokeep = new List<int>(currentSolution.listOfRoutes[routeindextoshuffle].nodesArray);
            halftokeep.Remove(0); //remove depot from beginning and end
            halftokeep.Remove(0);
            for (int j = 0; j <= halflength - 1; j++)
            {
                halftokeep.RemoveAt(0);             
            }

            //create a new route
            List<int> shuffledhalfroute = new List<int>();
            List<int> newroutearray = new List<int>();
            VehicleRoute newroute = new VehicleRoute(newroutearray);         
           
            //update new route characteristics - total demand (this will be the same before and after shuffle)
            newroute._totalDemandOnRoute = currentSolution.listOfRoutes[routeindextoshuffle].totalDemandOnRoute;                             
            Random rnd = new Random();        
            //add a shuffled 1st half of the route to the new, shuffled route
            while (halftoshuffle.Count > 0)
            {
                    int index = rnd.Next(0, halftoshuffle.Count); //pick a random item from the original route list
                    shuffledhalfroute.Add(halftoshuffle[index]); //place it at the end of the shuffled route
                    halftoshuffle.RemoveAt(index);//remove from half to shuffle
            }
                
            //add remainder of the original route to the shuffled route
            newroutearray = shuffledhalfroute.Concat(halftokeep).ToList(); 
            newroutearray.Insert(0, 0);//add back the depot beginning and end
            newroutearray.Add(0);
                
            //update new route characteristics - list of nodes
            newroute.nodesArray = newroutearray;      
          
            //update new route characteristics - total distance
                double TotalDistanceOnRoute = 0;        
                for (int r = 0; r < newroute.GetNumberOfNodesVisited() + 1; r++)
                {
                        TotalDistanceOnRoute += Program.vrpData.Distances[newroute.nodesArray[r], newroute.nodesArray[r + 1]];
  
                }
             newroute.totalDistanceOfRoute = TotalDistanceOnRoute;
             currentSolution.listOfRoutes[routeindextoshuffle] = newroute;
             double cost = 0;

             for (int k = 0; k < currentSolution.listOfRoutes.Count; k++)
             {
                 cost += currentSolution.listOfRoutes[k].totalDistanceOfRoute;
             }
             currentSolution.totalCost=cost;
             currentSolution.FeasibilityCheck();      
        }

        public static CVRPSolution RouteReduction(CVRPSolution currentSolution, CVRPData data)
        {
            //store currentSolution
            CVRPSolution AfterRouteReduction = new CVRPSolution(currentSolution);

            //find route of currentSolution with least capacity
            int indexofleastcapacityroute = -1;
            double demandofleastcapacityroute = 10000000000;
            for (int r = 0; r < currentSolution.listOfRoutes.Count(); r++)
            {
                if (currentSolution.listOfRoutes[r].totalDemandOnRoute < demandofleastcapacityroute)
                {
                    indexofleastcapacityroute = r;
                    demandofleastcapacityroute = currentSolution.listOfRoutes[r].totalDemandOnRoute;
                }
            }

            //sort leastcapacityroute by demand at each node
            List<int> routetoremove = new List<int>(currentSolution.listOfRoutes[indexofleastcapacityroute].nodesArray);
            routetoremove.Remove(0); //remove depot from beginning and end
            routetoremove.Remove(0);
            routetoremove = routetoremove.OrderByDescending(x => data.Demands[x]).ToList();

            //remove least cost route from current solution
            currentSolution.listOfRoutes.RemoveAt(indexofleastcapacityroute);
            int numadded = 0; 

            //for each node on the route to remove, add it to an existing route in the solution
            foreach (var node in routetoremove)
            {
                for (int k = 0; k < currentSolution.listOfRoutes.Count(); k++)
                {
                    if (k != indexofleastcapacityroute) //make sure the route isn't the route to remove
                    {
                        if (currentSolution.listOfRoutes[k].totalDemandOnRoute + data.Demands[node] < data.Capacity) //check feasibility
                        {
                            currentSolution.listOfRoutes[k].InsertNodeAt(1, node); //insert node as first stop on route
                            //update demand on route
                            currentSolution.listOfRoutes[k]._totalDemandOnRoute = currentSolution.listOfRoutes[k].totalDemandOnRoute + data.Demands[node];
                            //update cost of route
                            double TotalDistanceOnRoute = 0;
                            for (int p = 0; p < currentSolution.listOfRoutes[k].GetNumberOfNodesVisited() + 1; p++)
                            {
                               TotalDistanceOnRoute += Program.vrpData.Distances[currentSolution.listOfRoutes[k].nodesArray[p], currentSolution.listOfRoutes[k].nodesArray[p + 1]];
                            }
                            currentSolution.listOfRoutes[k].totalDistanceOfRoute = TotalDistanceOnRoute;
                            numadded = numadded + 1; 
                            break; //once a feasible alternate route is found, move to next node in routetoremove list
                        }
                    }
                }
            }

                //check to make sure new solution is feasible
                int feasible = currentSolution.FeasibilityCheck();

                //return original if new solution not feasible, otherwise return new solution
                if (feasible == 1)
                {
                    //update total cost of current solution
                    double cost = 0;
                    for (int k = 0; k < currentSolution.listOfRoutes.Count; k++)
                    {
                        cost += currentSolution.listOfRoutes[k].totalDistanceOfRoute;
                    }
                    currentSolution.totalCost = cost;
                    return currentSolution;
                }
                else
                {
                    return AfterRouteReduction; //return unchanged solution
                }
         }

        //Here we add a function which will take place of the jump function and also provide a reasonable neighborhood
       
        public static CVRPSolution superjump(CVRPData data, CVRPSolution currentsolution,int numofroutes)// This function will extract the information from the current solution to CVRPdata
        {
            //data provide all the original information
            //here we only need to read all the nodes from the routes_can
            CVRPSolution solution_temp = new CVRPSolution(currentsolution);

            CVRPData newvrpdata = new CVRPData();
            
            List<int> nodes = new List<int>();    // use this list to record all the nodes in those two routes

            List<VehicleRoute> routes = currentsolution.listOfRoutes;
            List<VehicleRoute> routes_can = new List<VehicleRoute>();

            solution_temp.listOfRoutes.Sort(delegate(VehicleRoute a, VehicleRoute b)// should be in decending order
            {
               return b.totalDistanceOfRoute.CompareTo(a.totalDistanceOfRoute);//decending
               //return a.totalDistanceOfRoute.CompareTo(b.totalDistanceOfRoute);//increasing
            });

            if (numofroutes > solution_temp.listOfRoutes.Count) //only merge half of the routes
            {
                numofroutes = solution_temp.listOfRoutes.Count / 2 + 1;
            }

            for (int i = 0; i < numofroutes; i++) //only pick the routes with top numofroutes hightest cost
            {

                routes_can.Add(solution_temp.listOfRoutes[i]);
                solution_temp.listOfRoutes.Remove(solution_temp.listOfRoutes[i]);
            }

            nodes.Add(0);
            for (int i = 0; i < routes_can.Count; i++) // go over all the route
            {
                foreach (int value in routes_can[i].nodesArray)
                {
                    if (value != 0)
                    {
                        nodes.Add(value);
                    }
                }
            }            
            //nodes store all the information of the nodes information
            newvrpdata.Dimension = nodes.Count;
            newvrpdata.Capacity = data.Capacity;
            newvrpdata.Demands=new double [newvrpdata.Dimension];
            for (int i = 0; i < nodes.Count; i++)
            {
                newvrpdata.Demands[i] = data.Demands[nodes[i]];
            }
            newvrpdata.Distances=new double[newvrpdata.Dimension,newvrpdata.Dimension];
            for (int i = 0; i < nodes.Count; i++)
            {
                for (int j = 0; j < nodes.Count; j++)
                {
                    newvrpdata.Distances[i, j] = data.Distances[nodes[i], nodes[j]];
                }
            }
            //this function return the solution by subset of reward nodes

            CVRPSolution partsolution = Program.SavingsMethodHeuristic(newvrpdata);


            //need to convert the solution back
            for(int i=0; i<partsolution.listOfRoutes.Count; i++)
            {
                for (int j = 0; j < partsolution.listOfRoutes[i].nodesArray.Count; j++)
                {
                    if (partsolution.listOfRoutes[i].nodesArray[j] != 0)
                    {
                        partsolution.listOfRoutes[i].nodesArray[j] = nodes[partsolution.listOfRoutes[i].nodesArray[j]];
                    }
                }
            }

            for (int i = 0; i < partsolution.listOfRoutes.Count; i++)
            {
                solution_temp.listOfRoutes.Add(partsolution.listOfRoutes[i]);
            }


            double cost = 0;

            for (int i = 0; i < solution_temp.listOfRoutes.Count; i++)
            {
                for (int r = 0; r < solution_temp.listOfRoutes[i].nodesArray.Count-1; r++)
                {

                    cost += Program.vrpData.Distances[solution_temp.listOfRoutes[i].nodesArray[r], solution_temp.listOfRoutes[i].nodesArray[r + 1]];

                }
            }


            solution_temp.totalCost = cost;
            
            solution_temp.FeasibilityCheck();
            return solution_temp;
            
        }

        public static CVRPSolution superjump_capacity(CVRPData data, CVRPSolution currentsolution, int numofroutes)// This function will extract the information from the current solution to CVRPdata
        {
            //data provide all the original information
            //here we only need to read all the nodes from the routes_can
            CVRPSolution solution_temp = new CVRPSolution(currentsolution);

            CVRPData newvrpdata = new CVRPData();

            List<int> nodes = new List<int>();    // use this list to record all the nodes in those two routes

            List<VehicleRoute> routes = currentsolution.listOfRoutes;
            List<VehicleRoute> routes_can = new List<VehicleRoute>();

            solution_temp.listOfRoutes.Sort(delegate(VehicleRoute a, VehicleRoute b)// should be in increasing
            {
                 return a.totalDemandOnRoute.CompareTo(b.totalDemandOnRoute);// increasing
               //return b.totalDemandOnRoute.CompareTo(a.totalDemandOnRoute);// decreasing
            });

            if (numofroutes > solution_temp.listOfRoutes.Count) //only merge half of the routes
            {
                numofroutes = solution_temp.listOfRoutes.Count / 2 + 1;
            }

            for (int i = 0; i < numofroutes; i++) //only pick the routes with top 2 hightest cost
            {
                routes_can.Add(solution_temp.listOfRoutes[i]);
                solution_temp.listOfRoutes.Remove(solution_temp.listOfRoutes[i]);
            }

            nodes.Add(0);
            for (int i = 0; i < routes_can.Count; i++) // go over all the route
            {
                foreach (int value in routes_can[i].nodesArray)
                {
                    if (value != 0)
                    {
                        nodes.Add(value);
                    }
                }
            }
            //nodes store all the information of the nodes information
            newvrpdata.Dimension = nodes.Count;
            newvrpdata.Capacity = data.Capacity;
            newvrpdata.Demands = new double[newvrpdata.Dimension];
            for (int i = 0; i < nodes.Count; i++)
            {
                newvrpdata.Demands[i] = data.Demands[nodes[i]];
            }
            newvrpdata.Distances = new double[newvrpdata.Dimension, newvrpdata.Dimension];
            for (int i = 0; i < nodes.Count; i++)
            {
                for (int j = 0; j < nodes.Count; j++)
                {
                    newvrpdata.Distances[i, j] = data.Distances[nodes[i], nodes[j]];
                }
            }
            //this function return the solution by subset of reward nodes

            CVRPSolution partsolution = Program.SavingsMethodHeuristic(newvrpdata);

            //need to convert the solution back
            for (int i = 0; i < partsolution.listOfRoutes.Count; i++)
            {
                for (int j = 0; j < partsolution.listOfRoutes[i].nodesArray.Count; j++)
                {
                    if (partsolution.listOfRoutes[i].nodesArray[j] != 0)
                    {
                        partsolution.listOfRoutes[i].nodesArray[j] = nodes[partsolution.listOfRoutes[i].nodesArray[j]];
                    }
                }
            }

            for (int i = 0; i < partsolution.listOfRoutes.Count; i++)
            {
                solution_temp.listOfRoutes.Add(partsolution.listOfRoutes[i]);
            }

            double cost = 0;

            for (int i = 0; i < solution_temp.listOfRoutes.Count; i++)
            {
                for (int r = 0; r < solution_temp.listOfRoutes[i].nodesArray.Count-1; r++)
                {

                    cost += Program.vrpData.Distances[solution_temp.listOfRoutes[i].nodesArray[r], solution_temp.listOfRoutes[i].nodesArray[r + 1]];

                }
            }

            solution_temp.totalCost = cost;
            solution_temp.FeasibilityCheck();
            return solution_temp;

        }
        public static CVRPSolution saving_improve(CVRPData data, CVRPSolution currentsolution)// this function try to improve the original saving method by reoptimize two subproblem
        {
            //data provide all the original information
            //here we only need to read all the nodes from the routes_can
            CVRPSolution solution_temp = new CVRPSolution(currentsolution);

            CVRPData newvrpdata = new CVRPData();
            CVRPData newvrpdata2 = new CVRPData();

            List<int> nodes = new List<int>();    // use this list to record all the nodes in the first half of routes
            List<int> nodes2 = new List<int>();    // use this list to record all the nodes in the second half of routes

            List<VehicleRoute> routes = currentsolution.listOfRoutes;
            List<VehicleRoute> routes_can = new List<VehicleRoute>();

            solution_temp.listOfRoutes.Sort(delegate(VehicleRoute a, VehicleRoute b)// should be in decending order
            {
                return b.totalDemandOnRoute.CompareTo(a.totalDemandOnRoute);
            });


            for (int i = 0; i < currentsolution.listOfRoutes.Count/4; i++) //pick first quarter of the routes
            {
                routes_can.Add(solution_temp.listOfRoutes[i]);
                solution_temp.listOfRoutes.Remove(solution_temp.listOfRoutes[i]);
            }

            for (int i = solution_temp.listOfRoutes.Count-1; i > currentsolution.listOfRoutes.Count/4; i--) //pick last quarter of the routes
            {
                routes_can.Add(solution_temp.listOfRoutes[i]);
                solution_temp.listOfRoutes.Remove(solution_temp.listOfRoutes[i]);
            }

            // initialize all the nodes on the first half of the routes
            nodes.Add(0);
            for (int i = 0; i < routes_can.Count; i++) // go over all the routes
            {
                foreach (int value in routes_can[i].nodesArray)
                {
                    if (value != 0)
                    {
                        nodes.Add(value);
                    }
                }
            }
            //initilize all the nodes on the second half of the routes
            nodes2.Add(0);
            for (int i = 0; i < solution_temp.listOfRoutes.Count; i++) // go over all the routes
            {
                foreach (int value in solution_temp.listOfRoutes[i].nodesArray)
                {
                    if (value != 0)
                    {
                        nodes2.Add(value);
                    }
                }
            }

            //nodes store all the information of the nodes information
            newvrpdata.Dimension = nodes.Count;
            newvrpdata.Capacity = data.Capacity;
            newvrpdata.Demands = new double[newvrpdata.Dimension];
            for (int i = 0; i < nodes.Count; i++)
            {
                newvrpdata.Demands[i] = data.Demands[nodes[i]];
            }
            newvrpdata.Distances = new double[newvrpdata.Dimension, newvrpdata.Dimension];
            for (int i = 0; i < nodes.Count; i++)
            {
                for (int j = 0; j < nodes.Count; j++)
                {
                    newvrpdata.Distances[i, j] = data.Distances[nodes[i], nodes[j]];
                }
            }

            //to store the second part of the solution
            newvrpdata2.Dimension = nodes2.Count;
            newvrpdata2.Capacity = data.Capacity;
            newvrpdata2.Demands = new double[newvrpdata2.Dimension];
            for (int i = 0; i < nodes2.Count; i++)
            {
                newvrpdata2.Demands[i] = data.Demands[nodes2[i]];
            }
            newvrpdata2.Distances = new double[newvrpdata2.Dimension, newvrpdata2.Dimension];
            for (int i = 0; i < nodes2.Count; i++)
            {
                for (int j = 0; j < nodes2.Count; j++)
                {
                    newvrpdata2.Distances[i, j] = data.Distances[nodes2[i], nodes2[j]];
                }
            }

            
            //this function return the solution by subset of reward nodes

            CVRPSolution partsolution = Program.SavingsMethodHeuristic(newvrpdata);
            CVRPSolution partsolution2 = Program.SavingsMethodHeuristic(newvrpdata2);

            //need to convert the solution back
            for (int i = 0; i < partsolution.listOfRoutes.Count; i++)
            {
                for (int j = 0; j < partsolution.listOfRoutes[i].nodesArray.Count; j++)
                {
                    if (partsolution.listOfRoutes[i].nodesArray[j] != 0)
                    {
                        partsolution.listOfRoutes[i].nodesArray[j] = nodes[partsolution.listOfRoutes[i].nodesArray[j]];
                    }
                }
            }

            //convert the second part solution back
            for (int i = 0; i < partsolution2.listOfRoutes.Count; i++)
            {
                for (int j = 0; j < partsolution2.listOfRoutes[i].nodesArray.Count; j++)
                {
                    if (partsolution2.listOfRoutes[i].nodesArray[j] != 0)
                    {
                        partsolution2.listOfRoutes[i].nodesArray[j] = nodes2[partsolution2.listOfRoutes[i].nodesArray[j]];
                    }
                }
            }
            //Merge all the route together
            for (int i = 0; i < partsolution.listOfRoutes.Count; i++)
            {
                partsolution2.listOfRoutes.Add(partsolution.listOfRoutes[i]);
            }

            double cost = 0;

            for (int i = 0; i < partsolution2.listOfRoutes.Count; i++)
            {
                for (int r = 0; r <partsolution2.listOfRoutes[i].nodesArray.Count-1; r++)
                {

                    cost += Program.vrpData.Distances[partsolution2.listOfRoutes[i].nodesArray[r], partsolution2.listOfRoutes[i].nodesArray[r + 1]];

                }
            }

            partsolution2.totalCost = cost;
            partsolution2.FeasibilityCheck();
            return partsolution2;
        }




    }
}
